<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>斐波拉契数列</title>
</head>
<body>
    
</body>
</html>
<script>
    // 1.递归法    0 1 2 3 5 8 13 21

    // function fibonacci(n) {
    //     if(n < 2) {
    //         return n;
    //     }
    //     return fibonacci(n-1) + fibonacci(n-2);
    // }

    // 2. 递归加记忆法
    // function fibonacci(n, memory = []) {
    //     if(n < 2) {
    //         return n;
    //     }

    //     if(!memory[n]) {
    //         console.log(memory)
    //         memory[n] = fibonacci(n-1, memory) + fibonacci(n-2,memory);
    //     }
    //     return memory[n]
    // }

    // 3.动态规划解读
    function fibonacci(n) {
        if(n < 2) {
            return n;
        }
        let i = 1;
        let pre = 0;
        let current = 1;
        let result = 0;
        while(i++ < n) {
            result = pre + current;
            pre = current;
            current = result;
        }

        return result;
    }

    console.log(fibonacci(8));
</script>